{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Can You Eat Your Favorite Candy on Your Favorite Day?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canEat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #你能在你最喜欢的那天吃到你最喜欢的糖果吗？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的正整数数组 <code>candiesCount</code> ，其中 <code>candiesCount[i]</code> 表示你拥有的第 <code>i</code> 类糖果的数目。同时给你一个二维数组 <code>queries</code> ，其中 <code>queries[i] = [favoriteType<sub>i</sub>, favoriteDay<sub>i</sub>, dailyCap<sub>i</sub>]</code> 。</p>\n",
    "\n",
    "<p>你按照如下规则进行一场游戏：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你从第 <code><strong>0</strong></code><strong> </strong>天开始吃糖果。</li>\n",
    "\t<li>你在吃完 <strong>所有</strong> 第 <code>i - 1</code> 类糖果之前，<strong>不能</strong> 吃任何一颗第 <code>i</code> 类糖果。</li>\n",
    "\t<li>在吃完所有糖果之前，你必须每天 <strong>至少</strong> 吃 <strong>一颗</strong> 糖果。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你构建一个布尔型数组 <code>answer</code> ，用以给出 <code>queries</code> 中每一项的对应答案。此数组满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>answer.length == queries.length</code> 。<code>answer[i]</code> 是 <code>queries[i]</code> 的答案。</li>\n",
    "\t<li><code>answer[i]</code> 为 <code>true</code> 的条件是：在每天吃 <strong>不超过</strong> <code>dailyCap<sub>i</sub></code><sub> </sub>颗糖果的前提下，你可以在第 <code>favoriteDay<sub>i</sub></code> 天吃到第 <code>favoriteType<sub>i</sub></code> 类糖果；否则 <code>answer[i]</code> 为 <code>false</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>注意，只要满足上面 3 条规则中的第二条规则，你就可以在同一天吃不同类型的糖果。</p>\n",
    "\n",
    "<p>请你返回得到的数组<em> </em><code>answer</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]\n",
    "<b>输出：</b>[true,false,true]\n",
    "<strong>提示：</strong>\n",
    "1- 在第 0 天吃 2 颗糖果(类型 0），第 1 天吃 2 颗糖果（类型 0），第 2 天你可以吃到类型 0 的糖果。\n",
    "2- 每天你最多吃 4 颗糖果。即使第 0 天吃 4 颗糖果（类型 0），第 1 天吃 4 颗糖果（类型 0 和类型 1），你也没办法在第 2 天吃到类型 4 的糖果。换言之，你没法在每天吃 4 颗糖果的限制下在第 2 天吃到第 4 类糖果。\n",
    "3- 如果你每天吃 1 颗糖果，你可以在第 13 天吃到类型 2 的糖果。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]\n",
    "<b>输出：</b>[false,true,true,false,false]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= candiesCount.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= candiesCount[i] <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= queries.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queries[i].length == 3</code></li>\n",
    "\t<li><code>0 <= favoriteType<sub>i</sub> < candiesCount.length</code></li>\n",
    "\t<li><code>0 <= favoriteDay<sub>i</sub> <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 <= dailyCap<sub>i</sub> <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [can-you-eat-your-favorite-candy-on-your-favorite-day](https://leetcode.cn/problems/can-you-eat-your-favorite-candy-on-your-favorite-day/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [can-you-eat-your-favorite-candy-on-your-favorite-day](https://leetcode.cn/problems/can-you-eat-your-favorite-candy-on-your-favorite-day/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,4,5,3,8]\\n[[0,2,2],[4,2,4],[2,13,1000000000]]', '[5,2,6,4,1]\\n[[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        n, m = len(candiesCount), len(queries)\n",
    "        pre = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + candiesCount[i]\n",
    "        \n",
    "        def jiaoji(a,b):\n",
    "            if not a or not b:\n",
    "                return []\n",
    "            a0, a1 = a[0], a[-1]\n",
    "            b0, b1 = b[0], b[-1]\n",
    "            if a0 <= b0 and b0 <= a1:\n",
    "                return [b0, min(a1, b1)]\n",
    "            elif b0 <= a0 and a0 <= b1:\n",
    "                return [a0, min(b1, a1)]\n",
    "            else:\n",
    "                return []\n",
    "        print(pre)\n",
    "\n",
    "        ans = [False] * m\n",
    "        for i, qi in enumerate(queries):\n",
    "            fti, fdi, dci = qi\n",
    "\n",
    "            #xianzhi1 = [pre[fdi], pre[fdi+1] - 1]\n",
    "            xianzhi2 = [pre[fti], pre[fti+1] - 1]\n",
    "            xianzhi3 = [fdi, dci * (fdi+1)-1]\n",
    "            die1 = jiaoji(xianzhi3, xianzhi2)\n",
    "            #die2 = jiaoji(die1, xianzhi3)\n",
    "            # if i == 30:\n",
    "            #     print(xianzhi2,xianzhi3)\n",
    "            # if i == 30:\n",
    "            #     print(die1)\n",
    "            if len(die1):\n",
    "                ans[i] = True\n",
    "        return ans\n",
    "            # # 前fdi-1天至少需要吃的糖果数量\n",
    "            # pre[fdi]\n",
    "            # # 前fdi-1天至多可以吃的糖果数量\n",
    "            # pre[fdi+1] - 1\n",
    "            # # 种类的限制\n",
    "            # # 前fdi-1天至多可以吃的糖果数量\n",
    "            # pre[fti]\n",
    "            # # 前fdi-1天至多可以吃的糖果数量\n",
    "            # pre[fti+1] - 1\n",
    "            # # 吃货能力的限制\n",
    "            # # 前fdi-1天至多能吃\n",
    "            # dci * fdi-1\n",
    "            # # 前fdi-1天至少能吃\n",
    "            # fdi - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        n, m = len(candiesCount), len(queries)\n",
    "        pre = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + candiesCount[i]\n",
    "        \n",
    "        def jiaoji(a,b):\n",
    "            if not a or not b:\n",
    "                return False\n",
    "            a0, a1 = a[0], a[-1]\n",
    "            b0, b1 = b[0], b[-1]\n",
    "            if (a0 <= b0 and b0 <= a1) or (b0 <= a0 and a0 <= b1):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        ans = [False] * m\n",
    "        for i, qi in enumerate(queries):\n",
    "            fti, fdi, dci = qi\n",
    "            xianzhi1 = [pre[fti], pre[fti+1] - 1]\n",
    "            xianzhi2 = [fdi, dci * (fdi+1)-1]\n",
    "            if jiaoji(xianzhi1, xianzhi2):\n",
    "                ans[i] = True\n",
    "        return ans\n",
    "            # # 前fdi-1天至少需要吃的糖果数量\n",
    "            # pre[fdi]\n",
    "            # # 前fdi-1天至多可以吃的糖果数量\n",
    "            # pre[fdi+1] - 1\n",
    "            # # 种类的限制\n",
    "            # # 前fdi-1天至多可以吃的糖果数量\n",
    "            # pre[fti]\n",
    "            # # 前fdi-1天至多可以吃的糖果数量\n",
    "            # pre[fti+1] - 1\n",
    "            # # 吃货能力的限制\n",
    "            # # 前fdi-1天至多能吃\n",
    "            # dci * fdi-1\n",
    "            # # 前fdi-1天至少能吃\n",
    "            # fdi - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        n, m = len(candiesCount), len(queries)\n",
    "        pre = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + candiesCount[i]\n",
    "        \n",
    "        def jiaoji(a,b):\n",
    "            a0, a1 = a[0], a[-1]\n",
    "            b0, b1 = b[0], b[-1]\n",
    "            if (a0 <= b0 and b0 <= a1) or (b0 <= a0 and a0 <= b1):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        ans = [False] * m\n",
    "        for i, qi in enumerate(queries):\n",
    "            fti, fdi, dci = qi\n",
    "            xianzhi1 = [pre[fti], pre[fti+1] - 1]\n",
    "            xianzhi2 = [fdi, dci * (fdi+1)-1]\n",
    "            if jiaoji(xianzhi1, xianzhi2):\n",
    "                ans[i] = True\n",
    "        return ans\n",
    "            # # 前fdi-1天至少需要吃的糖果数量\n",
    "            # pre[fdi]\n",
    "            # # 前fdi-1天至多可以吃的糖果数量\n",
    "            # pre[fdi+1] - 1\n",
    "            # # 种类的限制\n",
    "            # # 前fdi-1天至多可以吃的糖果数量\n",
    "            # pre[fti]\n",
    "            # # 前fdi-1天至多可以吃的糖果数量\n",
    "            # pre[fti+1] - 1\n",
    "            # # 吃货能力的限制\n",
    "            # # 前fdi-1天至多能吃\n",
    "            # dci * fdi-1\n",
    "            # # 前fdi-1天至少能吃\n",
    "            # fdi - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]])->List[bool]:\n",
    "        n = len(queries)\n",
    "        ans = [False] * n\n",
    "        pre_sm = list(accumulate(candiesCount, initial=0))\n",
    "        for i, (x, y, z) in enumerate(queries):\n",
    "            right = pre_sm[x+1]-1\n",
    "            left = (pre_sm[x]//z)\n",
    "            if left<=y<=right:\n",
    "                ans[i] = True\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        total = [0]+list(accumulate(candiesCount))\n",
    "        ans=[]\n",
    "        for t,d,c in queries:\n",
    "            if c*(d+1)<=total[t] or (d+1)>total[t+1]:\n",
    "                ans.append(False)\n",
    "            else:\n",
    "                ans.append(True)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        a = list(accumulate(candiesCount, initial=0))\n",
    "        ans = [False] * len(queries)\n",
    "        for i, (t, d, c) in enumerate(queries):\n",
    "            if a[t + 1] >= d + 1 and d * c + c - 1 >= a[t]:\n",
    "                ans[i] = True\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        m = len(queries)\n",
    "        ans = [False]*m\n",
    "        add_sum = list(accumulate(candiesCount,initial=0))\n",
    "        for i in range(m):\n",
    "            ftype,fday,cap = queries[i]\n",
    "            late_time = add_sum[ftype+1]-1\n",
    "            small_time = add_sum[ftype]//cap\n",
    "            if small_time<=fday<=late_time:\n",
    "                ans[i] = True\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        # 前缀和\n",
    "        total = list(accumulate(candiesCount))\n",
    "        \n",
    "        ans = list()\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            x1 = favoriteDay + 1\n",
    "            y1 = (favoriteDay + 1) * dailyCap\n",
    "            x2 = 1 if favoriteType == 0 else total[favoriteType - 1] + 1\n",
    "            y2 = total[favoriteType]\n",
    "            \n",
    "            ans.append(not(x1 > y2 or y1 < x2))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        \"\"\"\n",
    "            candiesCount = [7, 4, 5, 3, 8]\n",
    "            queries = [[0, 2, 2], [4, 2, 4], [2, 13, 1000000]]\n",
    "            每天至少吃 1 颗糖，最多吃 dailyCap 颗糖，\n",
    "            吃糖果的总数在区间 [favouriteDay_i+1, (favouriteDay_i+1)*dailyCapi]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        prefix_sum = list(accumulate(candiesCount, initial=0))\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            # range1\n",
    "            x1 = favoriteDay + 1\n",
    "            y1 = (favoriteDay + 1) * dailyCap\n",
    "\n",
    "            # range2\n",
    "            x2 = prefix_sum[favoriteType] + 1\n",
    "            y2 = prefix_sum[favoriteType+1]\n",
    "\n",
    "            res.append(not(x2 > y1 or x1 > y2))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        # [1, queries[i][2]]\n",
    "        # for eating t type candy\n",
    "        # fastest floor(sum[t]) + 1\n",
    "        # slowest sum[t+1]\n",
    "        n = len(candiesCount)\n",
    "        m = len(queries)\n",
    "        presum = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            presum[i] = presum[i-1] + candiesCount[i-1]\n",
    "        ans = [False] * m\n",
    "        for i in range(m):\n",
    "            t = queries[i][0]\n",
    "            d = queries[i][1] + 1\n",
    "            c = queries[i][2]\n",
    "            a = presum[t] // c + 1\n",
    "            b = presum[t+1]\n",
    "            ans[i] = a <= d and d <= b\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]])->List[bool]:\n",
    "        n = len(queries)\n",
    "        ans = [False] * n\n",
    "        pre_sm = list(accumulate(candiesCount, initial=0))\n",
    "        for i, (x, y, z) in enumerate(queries):\n",
    "            right = pre_sm[x+1]\n",
    "            left = (pre_sm[x]//z)+1\n",
    "            if left<=y+1<=right:\n",
    "                ans[i] = True\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        # 类型，第day天，最多cap颗\n",
    "        def judge(type_, day, cap):\n",
    "            return pre[type_] < (day + 1) * cap and pre[type_ + 1] - 1 >= day\n",
    "\n",
    "        pre = [0]\n",
    "        for c in candiesCount:\n",
    "            pre.append(pre[-1] + c)\n",
    "        ans = [judge(a, b, c) for a, b, c in queries]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        pre_sum = list(itertools.accumulate(candiesCount, initial=0)) \n",
    "        return [pre_sum[i] <= (d+1) * m - 1 and pre_sum[i+1] > d for i, d, m in queries] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        # 前缀和\n",
    "        total = list(accumulate(candiesCount))\n",
    "        \n",
    "        ans = list()\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            x1 = favoriteDay + 1\n",
    "            y1 = (favoriteDay + 1) * dailyCap\n",
    "            x2 = 1 if favoriteType == 0 else total[favoriteType - 1] + 1\n",
    "            y2 = total[favoriteType]\n",
    "            \n",
    "            ans.append(not(x1 > y2 or y1 < x2))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        presum = [0]\n",
    "        for candy in candiesCount:\n",
    "            presum.append(presum[-1] + candy)\n",
    "        result = []\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            left, right = favoriteDay+1, (favoriteDay+1)*dailyCap\n",
    "            lower, upper = presum[favoriteType]+1, presum[favoriteType+1]\n",
    "            result.append(not (right < lower or left > upper))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        total = list(accumulate(candiesCount))\n",
    "        \n",
    "        ans = list()\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            x1 = favoriteDay + 1\n",
    "            y1 = (favoriteDay + 1) * dailyCap\n",
    "            x2 = 1 if favoriteType == 0 else total[favoriteType - 1] + 1\n",
    "            y2 = total[favoriteType]\n",
    "            \n",
    "            ans.append(not(x1 > y2 or y1 < x2))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        presum = [0]\n",
    "        for candy in candiesCount:\n",
    "            presum.append(presum[-1] + candy)\n",
    "        result = []\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            left, right = favoriteDay+1, (favoriteDay+1)*dailyCap\n",
    "            lower, upper = presum[favoriteType]+1, presum[favoriteType+1]\n",
    "            result.append(not (right < lower or left > upper))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "      total = list(accumulate(candiesCount))\n",
    "      ans = []\n",
    "      for favoriteType, favoriteDay, dailyCap in queries:\n",
    "        x1 = favoriteDay + 1\n",
    "        y1 = (favoriteDay + 1) * dailyCap\n",
    "        x2 = 1 if favoriteType == 0 else total[favoriteType - 1] + 1\n",
    "        y2 = total[favoriteType]\n",
    "        ans.append(not(x1 > y2 or y1 < x2))\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        # 第 favoriteDayi 天吃到第 favoriteTypei 类糖果的情况\n",
    "        # day+1,capi*(day+1)-1\n",
    "        d = list(accumulate(candiesCount))\n",
    "        #\n",
    "        ans = []\n",
    "        for types,day,capi in queries:\n",
    "            # 限制区间(糖果数量区间)\n",
    "            x1 = day+1\n",
    "            y1 = capi*(day+1)\n",
    "            # 糖果区间\n",
    "            x2 = 1 if types == 0 else d[types-1]+1\n",
    "            y2 = d[types]\n",
    "            ans.append(not (y2 < x1 or x2 > y1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        return [summ := list(accumulate(candiesCount, initial=0)), [max(summ[typ]+1,day+1) <= min(summ[typ+1],(day+1)*cap-1)  for typ,day,cap in queries] ][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(candiesCount)\n",
    "        pre_sum = []\n",
    "        cur_sum = 0\n",
    "        for i in range(n):\n",
    "            cur_sum += candiesCount[i]\n",
    "            pre_sum.append(cur_sum)\n",
    "\n",
    "        #print(pre_sum)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ft,fd,dc = q\n",
    "            x1 = fd + 1\n",
    "            y1 = (fd+1) * dc\n",
    "            x2 = 1 if ft == 0 else pre_sum[ft-1] + 1\n",
    "            y2 = pre_sum[ft]\n",
    "            ans.append(not(x1 > y2 or y1 < x2))\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        # 前缀和\n",
    "        total = list(accumulate(candiesCount))\n",
    "        ans = list()\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            x1 = favoriteDay + 1\n",
    "            y1 = (favoriteDay + 1) * dailyCap\n",
    "            x2 = 1 if favoriteType == 0 else total[favoriteType - 1] + 1\n",
    "            y2 = total[favoriteType]\n",
    "            ans.append(not(x1 > y2 or y1 < x2))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        m, n = len(queries), len(candiesCount)\n",
    "        ans = []\n",
    "        ps = list(accumulate(candiesCount, initial=0))\n",
    "\n",
    "        for t, d, c in queries:\n",
    "            if ps[t + 1] > d and (ps[t] + 1) <= (d + 1) * c:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        presum = [0]\n",
    "        for candy in candiesCount:\n",
    "            presum.append(presum[-1] + candy)\n",
    "        result = []\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            left, right = favoriteDay+1, (favoriteDay+1)*dailyCap\n",
    "            lower, upper = presum[favoriteType]+1, presum[favoriteType+1]\n",
    "            result.append(not (right < lower or left > upper))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        pre = list(accumulate(candiesCount, initial=0))\n",
    "        ans = []\n",
    "        for tp, day, cnt in queries:\n",
    "\n",
    "            high = pre[tp+1]-1  # 最晚\n",
    "            # 最早\n",
    "            low = pre[tp]//cnt\n",
    "            ans.append(low<=day<=high)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        # 前缀和\n",
    "        total = list(accumulate(candiesCount))\n",
    "        \n",
    "        ans = list()\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            x1 = favoriteDay + 1\n",
    "            y1 = (favoriteDay + 1) * dailyCap\n",
    "            x2 = 1 if favoriteType == 0 else total[favoriteType - 1] + 1\n",
    "            y2 = total[favoriteType]\n",
    "            \n",
    "            ans.append(not(x1 > y2 or y1 < x2))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        sum_l = []\n",
    "        sum_ = 0\n",
    "        for c in candiesCount:\n",
    "            sum_ += c\n",
    "            sum_l.append(sum_)\n",
    "        res = []\n",
    "        for t,d,c in queries:\n",
    "            max_ = sum_l[t]-1\n",
    "            sum0 = sum_l[t-1] if t-1>=0 else 0\n",
    "            min_ = sum0//c\n",
    "            if d>=min_ and d<=max_:\n",
    "                res.append(True)\n",
    "            else:\n",
    "                res.append(False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        \n",
    "        n = len(candiesCount)\n",
    "        pre = [0]\n",
    "        for num in candiesCount:\n",
    "            pre.append(pre[-1] + num)\n",
    "        print(pre)\n",
    "\n",
    "        def check(idx, t, k):\n",
    "            # 0-i-1最少需要消耗多少？pre[idx] - k + 1\n",
    "            # 0-i-1至多消耗多少？pre[idx + 1] - 1\n",
    "            return t <= pre[idx + 1] - 1 and k * t >= pre[idx] - k + 1\n",
    "        \n",
    "        ans = []\n",
    "        for idx, t, k in queries:\n",
    "            ans.append(check(idx, t, k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        ans = []\n",
    "        ps = list(accumulate(candiesCount, initial=0))\n",
    "\n",
    "        for t, d, c in queries:\n",
    "            if ps[t + 1] >= d + 1 and (ps[t] + 1) <= (d + 1) * c:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        # 前缀和\n",
    "        total = list(accumulate(candiesCount))\n",
    "        \n",
    "        ans = list()\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            x1 = favoriteDay + 1\n",
    "            y1 = (favoriteDay + 1) * dailyCap\n",
    "            x2 = 1 if favoriteType == 0 else total[favoriteType - 1] + 1\n",
    "            y2 = total[favoriteType]\n",
    "            \n",
    "            ans.append(not(x1 > y2 or y1 < x2))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        answer          = list()\n",
    "        preSumCandies   = [0]\n",
    "        for i in range(len(candiesCount)):\n",
    "            preSumCandies.append(preSumCandies[-1] + candiesCount[i])\n",
    "        for i in range(len(queries)):\n",
    "            fType   = queries[i][0]\n",
    "            fDay    = queries[i][1]\n",
    "            dCap    = queries[i][2]\n",
    "            dayMax  = preSumCandies[fType] + candiesCount[fType] \n",
    "            dayMin  = preSumCandies[fType] // dCap\n",
    "            if dayMin <= fDay < dayMax:\n",
    "                answer.append(True)\n",
    "            else:\n",
    "                answer.append(False)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(candiesCount)\n",
    "        preSum = [0 for _ in range(n + 7)]\n",
    "        for _ in range(n):\n",
    "            preSum[_] = candiesCount[_] + preSum[_ - 1]\n",
    "        ret = []\n",
    "        for x, y, z in queries:\n",
    "            ret.append((y + 1) * z > preSum[x - 1] and (y + 1) <= preSum[x])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        presum = [0]\n",
    "        for candy in candiesCount:\n",
    "            presum.append(presum[-1] + candy)\n",
    "        result = []\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            left, right = favoriteDay+1, (favoriteDay+1)*dailyCap\n",
    "            lower, upper = presum[favoriteType]+1, presum[favoriteType+1]\n",
    "            result.append(not (right < lower or left > upper))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        total = list(accumulate(candiesCount))\n",
    "        ans = list()\n",
    "        print(total)\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            x1 = favoriteDay + 1\n",
    "            y1 = (favoriteDay + 1) * dailyCap\n",
    "            \n",
    "            x2 = 1 if favoriteType == 0 else total[favoriteType - 1] + 1\n",
    "            y2 = total[favoriteType]\n",
    "            \n",
    "            ans.append(not(x1 > y2 or y1 < x2))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\r\n",
    "        s = list(accumulate(candiesCount, initial=0))\r\n",
    "        return [(d + 1) * dc > s[t] and d < s[t + 1] for t, d, dc in queries]\r\n",
    "        \r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]: \n",
    "        pre = [0]\n",
    "        for num in candiesCount:\n",
    "            pre.append(pre[-1] + num)\n",
    "            \n",
    "        ans = []\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            # 最小速度不会超过，最大速度可以到达\n",
    "            ans.append(favoriteDay + 1 <= pre[favoriteType + 1] and dailyCap * (favoriteDay + 1) > pre[favoriteType])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        ans = []\n",
    "        candies_count = [0];tmp = 0\n",
    "        for j in range(len(candiesCount)):\n",
    "            tmp += candiesCount[j]\n",
    "            candies_count.append(tmp)\n",
    "        for i in range(len(queries)):\n",
    "            ans.append((queries[i][1]+1) <= candies_count[queries[i][0]+1] and candies_count[queries[i][0]] < (1+queries[i][1])*queries[i][2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(candiesCount)\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            pre[i] = pre[i-1] + candiesCount[i-1]\n",
    "        \n",
    "\n",
    "        def check(idx, t, k):\n",
    "            # 要第t天吃到种类为idx的糖\n",
    "            # 那么在t-1天最少要吃 pre[idx] - k + 1个糖\n",
    "            # 最多在t-1天吃掉pre[idx + 1] - 1个糖\n",
    "\n",
    "            return t * k >= pre[idx] - k + 1 and t <= pre[idx + 1] - 1\n",
    "        \n",
    "        ans = []\n",
    "        for idx, t, k in queries:\n",
    "            ans.append(check(idx, t, k))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        preSum = [0] * (len(candiesCount) + 1)\n",
    "        res = []\n",
    "        for i in range(len(candiesCount)):\n",
    "            preSum[i+1] = preSum[i] + candiesCount[i]\n",
    "        for candyType, day, cap in queries:\n",
    "            min_cap, max_cap = day + 1, cap * (day + 1)\n",
    "            first_candy,last_candy = preSum[candyType] + 1, preSum[candyType] + candiesCount[candyType]\n",
    "            res.append(min_cap <= last_candy and max_cap >= first_candy)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        pre_sum = list(accumulate(candiesCount, initial = 0))\n",
    "        ans = [False] * len(queries)\n",
    "        \n",
    "        for i, (t, q1, q2) in enumerate(queries):\n",
    "            right = pre_sum[t + 1]\n",
    "            left = (pre_sum[t] + q2) // q2\n",
    "            ans[i] = left <= q1 + 1 <= right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        answer          = list()\n",
    "        preSumCandies   = [0]\n",
    "        for i in range(len(candiesCount)):\n",
    "            preSumCandies.append(preSumCandies[-1] + candiesCount[i])\n",
    "        for i in range(len(queries)):\n",
    "            fType   = queries[i][0]\n",
    "            fDay    = queries[i][1]\n",
    "            dCap    = queries[i][2]\n",
    "            dayMax  = preSumCandies[fType] + candiesCount[fType] - 1\n",
    "            dayMin  = preSumCandies[fType] // dCap\n",
    "            if dayMin <= fDay <= dayMax:\n",
    "                answer.append(True)\n",
    "            else:\n",
    "                answer.append(False)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        ln1, ln2 = len(candiesCount), len(queries)\n",
    "        res = []\n",
    "        candies =[0]\n",
    "        for i in range(ln1):\n",
    "             candies.append(candies[i] + candiesCount[i])\n",
    "        for k in range(ln2):\n",
    "            [ft, fd, fc] = queries[k]\n",
    "            res.append(candies[ft+1] - fd >= 1 and fc*(fd + 1) - candies[ft] > 0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        preSum = [0] * (len(candiesCount) + 1)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for i in range(len(candiesCount)):\n",
    "\n",
    "            preSum[i+1] = preSum[i] + candiesCount[i]\n",
    "\n",
    "        for candyType, day, cap in queries:\n",
    "\n",
    "            min_cap, max_cap = day + 1, cap * (day + 1)\n",
    "\n",
    "            first_candy,last_candy = preSum[candyType] + 1, preSum[candyType] + candiesCount[candyType]\n",
    "\n",
    "            res.append(min_cap <= last_candy and max_cap >= first_candy)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        accs = [0]\n",
    "        for candy in candiesCount:\n",
    "            accs.append(accs[-1] + candy)\n",
    "        answer = [False] * len(queries)\n",
    "        for i, (ftype, fday, daycap) in enumerate(queries):\n",
    "            if fday * daycap + daycap - 1 >= accs[ftype] and accs[ftype + 1] >= fday + 1:\n",
    "                answer[i] = True\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(candiesCount)\n",
    "        s = [0] * n\n",
    "        s[0] = candiesCount[0]\n",
    "        for i in range(1, n):\n",
    "            s[i] = s[i - 1] + candiesCount[i]\n",
    "        ret = []\n",
    "        for typ, day, cap in queries:\n",
    "            mi = day + 1\n",
    "            ma = (day + 1) * cap\n",
    "            start = s[typ - 1] + 1 if typ > 0 else 1\n",
    "            end = s[typ]\n",
    "            ret.append( start <= ma and end >= mi)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        n = len(candiesCount)\n",
    "        pre_sum = []\n",
    "        cur_sum = 0\n",
    "        for i in range(n):\n",
    "            cur_sum += candiesCount[i]\n",
    "            pre_sum.append(cur_sum)\n",
    "\n",
    "        #print(pre_sum)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ft,fd,dc = q\n",
    "            if ft == 0:\n",
    "                if pre_sum[0] - fd*dc > 0:\n",
    "                    ans.append(True)\n",
    "                else:\n",
    "                    ans.append(False)\n",
    "                continue\n",
    "            minc = fd+1\n",
    "            maxc = (fd+1) * dc\n",
    "            if minc <= pre_sum[ft] <= maxc or minc <= pre_sum[ft-1]+1 <= maxc:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        preSum = [0] * (len(candiesCount) + 1)\n",
    "        res = []\n",
    "        for i in range(len(candiesCount)):\n",
    "            preSum[i+1] = preSum[i] + candiesCount[i]\n",
    "        for candyType, day, cap in queries:\n",
    "            min_cap, max_cap = day + 1, cap * (day + 1)\n",
    "            first_candy,last_candy = preSum[candyType] + 1, preSum[candyType] + candiesCount[candyType]\n",
    "            res.append(min_cap <= last_candy and max_cap >= first_candy)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        # 前缀和\n",
    "        total = list(accumulate(candiesCount))\n",
    "        \n",
    "        ans = list()\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            x1 = favoriteDay + 1\n",
    "            y1 = (favoriteDay + 1) * dailyCap\n",
    "            x2 = 1 if favoriteType == 0 else total[favoriteType - 1] + 1\n",
    "            y2 = total[favoriteType]\n",
    "            \n",
    "            ans.append(not(x1 > y2 or y1 < x2))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        preSum = [0] * (len(candiesCount) + 1)\n",
    "        res = []\n",
    "        for i in range(len(candiesCount)):\n",
    "            preSum[i+1] = preSum[i] + candiesCount[i]\n",
    "        for candyType, day, cap in queries:\n",
    "            min_cap, max_cap = day + 1, cap * (day + 1)\n",
    "            first_candy,last_candy = preSum[candyType] + 1, preSum[candyType] + candiesCount[candyType]\n",
    "            res.append(min_cap <= last_candy and max_cap >= first_candy)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
